Наибольший общий делитель многочленов

Пусть $F$ – поле и $f, g \in F[x]$. Многочлен $h \in F[x]$ называется **наибольшим общим делителем (НОД)** многочленов $f$ и $g$, если: 1. $h \mid f$ и $h \mid g$ 2. Для любого $p \in F[x]$ из условий $p \mid f$ и $p \mid g$ следует $p \mid h$. НОД многочленов определён с точностью до ассоциированности.

Для любых ненулевых многочленов $f$ и $g$ над полем $F$: 1. Существует наибольший общий делитель 2. Для некоторых многочленов $u, v \in F[x]$ выполняется равенство $$\operatorname{НОД}(f, g) = uf + vg$$

Рассмотрим множество: $$I := \{ uf + vg \mid u, v \in F[x] \}$$ Оно содержит ненулевые многочлены (например, $f$ и $g$). Пусть $d$ - ненулевой многочлен наименьшей степени в $I$. Покажем, что $I = \operatorname{НОД}(f, g)$ **Общий делитель:** Поделим $f$ на $d$ с остатком: $$f = qd + r,~~~~~\deg r < \deg d$$Так как $d = u_0f + v_0g$ для некоторых $u_0, v_0 \in F[x]$, то: $$r = f - qd = (1 - qu_0)f + (-qv_0)g \in I$$Из $\deg r < \deg d$ и минимальности степени $d$ следует $r = 0$, т.е. $d \mid f$. Аналогично доказывается $d \mid g$. **Свойство НОД:** Пусть $p \in F[x]$ делит $f$ и $g$. Тогда по свойствам делимости: $$p \mid (u_0f + v_0g) \implies p \mid d$$ Таким образом, $d = \operatorname{НОД}(f, g)$, и представление $d = uf + vg$ следует из построения множества $I$. $\square$

Пусть $d_{1}, d_{2}$ - $\operatorname{НОД}(f, g)$. Тогда $d_{1} \sim d_{2}$

По определению НОД: $$\left. \begin{array} \\ d_{1} \mid f ~\land~ d_{1} \mid g \\ d_{2} \mid f ~\land~ d_{2} \mid g \\ \forall{r}\mathpunct{:}~~ r \mid f ~\land~ r \mid g \implies r \mid d_{1} \\ \forall{r}\mathpunct{:}~~ r \mid f ~\land~ r \mid g \implies r \mid d_{2} \end{array} \right| \implies \begin{cases} d_{1} \mid d_{2} \\ d_{2} \mid d_{1} \end{cases} \iff d_{1} \sim d_{2}$$ $\square$